package leetcode.code;

import java.util.*;

/**
 * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: nums = [1,1,1,2,2,3], k = 2
 * 输出: [1,2]
 * 示例 2:
 *
 * 输入: nums = [1], k = 1
 * 输出: [1]
 *  
 *
 * 提示：
 *
 * 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
 * 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
 * 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
 * 你可以按任意顺序返回答案。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/top-k-frequent-elements
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class medium_前K个高频元素_最小堆 {
    static class Solution {
        public int[] topKFrequent_1(int[] nums, int k) {
            // build hash map : character and how often it appears
            HashMap<Integer, Integer> count = new HashMap();
            for (int n: nums) {
                count.put(n, count.getOrDefault(n, 0) + 1);
            }

            // init heap 'the less frequent element first'
            PriorityQueue<Integer> heap =
                    new PriorityQueue<Integer>((n1, n2) -> count.get(n1) - count.get(n2));

            // keep k top frequent elements in the heap
            for (int n: count.keySet()) {
                heap.add(n);
                if (heap.size() > k)
                    heap.poll();
            }
            int[] r = new int[k];
            int i = 0;
            while (!heap.isEmpty() && i < k)
                r[i++] = heap.poll();
            return r;
        }

        public int[] topKFrequent(int[] nums, int k) {
            List<int[]> l = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length;){
                int tmp = 1;
                int a = nums[i];
                while (++i<nums.length && nums[i]==a){
                    tmp++;
                }
                l.add(new int[]{a, tmp});
            }

            // init heap 'the less frequent element first'
            PriorityQueue<int[]> heap =
                    new PriorityQueue<int[]>((n1, n2) -> n1[1] - n2[1]);

            // keep k top frequent elements in the heap
            for (int[] n: l) {
                heap.add(n);
                if (heap.size() > k)
                    heap.poll();
            }
            int[] r = new int[k];
            int i = 0;
            while (!heap.isEmpty() && i < k)
                r[i++] = heap.poll()[0];
            return r;
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.topKFrequent(new int[]{1,1,1,2,3}, 2));
    }
}
